The present invention is related to a method for optimizing the testing of integrated circuits (IC) and, more particularly, to a method for improving the test coverage by identifying additional test points for be inserted in the IC under test.
Digital circuits are tested using a variety of strategies including functional test patterns, deterministic structural test patterns, and random patterns. Random pattern testing is particularly significant because it requires relatively little test data and can be accomplished not only by automated test equipment, but by the digital circuit itself using Built-in Self Test (BIST) circuitry. In order to achieve high random pattern testability, it is often necessary to modify a digital circuit design such that random patterns more easily detect potential defects in the IC under test.
One way of modifying digital circuits to improve random pattern testability is known as test point insertion. During test point insertion, additional logic and scannable latches are added to the logic to provide additional points of control or observation during testing. By way of example, and referring to FIG. 1, there is shown a random-resistant circuit, where the signal feeding the top input of the two input AND gate is nearly always 0 when random patterns are applied to the circuit, since the 16 input AND gate will produce a logic 1 only once every 216 random patterns. Such a path is rarely sensitized to allow faults to propagate through the bottom input of the downstream AND gate. Furthermore, faults in the downstream logic requiring a logic 1 for activation will be rarely be activated. If now, a control-1 test point is added to the circuit, the random pattern testability substantially improves.
Referring to FIG. 2, it is evident that adding an OR-gate driven by a scannable latch improves the probability that a logic 1 will appear on the top input to the 2-input AND gate, and will propagate to downstream logic to enable the detection of certain faults not otherwise tested. Additional faults will be allowed to propagate through the 2-input AND gate, and faults located in the downstream logic requiring a logic 1 for activation will have a much higher probability of being activated. This OR gate driven by a scannable latch is known as a control-1 test point. In other cases, a control-0 test point (implemented as an AND gate) or an observation point (implemented as a signal feeding a scannable latch) may be inserted. The problem being solved by this invention is to efficiently identify where test points should be inserted in the IC, and what type of test points should be added thereat.
Several solutions exist to the problem of test point identification. For instance, in an article by B. H. Seiss, P. M. Trouborst, and M. H. Schulz, xe2x80x9cTest Point Insertion for Scan-Based BIST,xe2x80x9d published in the Proceedings of the European Test Conference, pp. 253-262, 1991, a cost function gradient technique for inserting test points is described. This method is based on an earlier work by F. Brglez, published in the article xe2x80x9cOn Testability of Combinational Networksxe2x80x9d, Proceedings of International Symposium on Circuits and Systems, pp. 221-225, 1984, and on work by R. F. Lisanke, A. J. Brglez, A. J. DeGeus, xe2x80x9cTestability-Driven Random Test-Pattern Generationxe2x80x9d, published in the IEEE Transactions on CAD, Vol. CAD-6, November 1987, pp. 1082-1087, all of which are based on random pattern testability. The method described in the aforementioned articles selects one test point at a time from a set of candidate test points, which is chosen according to a set of criteria that estimates the improvement in random pattern testability if the test point were inserted. Each candidate test point is temporarily incorporated in the circuit, and the actual improvement in random pattern testability is measured. Once all of the candidates have been evaluated, the test point providing the largest increase in random pattern testability is added to the circuit. This process is repeated until the maximum number of test points is achieved, or until the circuit reaches a satisfactory level of random pattern testability.
The test point insertion algorithm described in U.S. Pat. No. 6,256,759, xe2x80x9cHybrid Algorithm for Test Point Selection for Scan-Based BIST,xe2x80x9d to S. K. Bhawmik, et al., improves the performance of the previously mentioned single test point insertion algorithm developed by Seiss et al. By recognizing that the effect of a test point is only significant in the area of logic immediately surrounding the test point, calculations used to determine the effect of a test point on random pattern testability can be reduced by considering only those nodes in the circuit for which the test point has a significant effect.
In U.S. Pat. Nos. 5,737,340 and 6,070,261, xe2x80x9cMulti-phase Test Point Insertion for Built-in Self Test of Integrated Circuitsxe2x80x9d, both to N. Tamarapalli, et al., a method for inserting test points into a logic circuit is described, wherein test points are enabled or disabled depending on certain control signals. Each combination of control signals is known as a phase. Additional logic is added to the chip to decode the control signals and to control the operation of the test points. The algorithm for determining test points uses probabilistic fault simulation to determine test point locations rather than way of a COP (Controllability/Observability Program) based approach used in the previously described articles. However, as in previous cases, the test point insertion algorithm determines the added test points one at a time.
The process of test point insertion is further enhanced by considering signal propagation delays through the various paths in the logic circuit, as described in U.S. Pat. No. 5,828,828, xe2x80x9cMethod For Inserting Test Points for Full and Partial Scan Built-in Self Testing,xe2x80x9d to Lin and Cheng. The insertion of a test point is disallowed if by doing so it introduces a signal delay that negatively impacts the performance of the circuit. In order to determine whether this situation occurs, the test point is assigned a delay value. For each node in the circuit, a signal slack is computed. (Note: signal slack is the amount of time by which a signal may be delayed before it must reach a specified node in the circuit). If the delay for the test point exceeds the signal slack for the node, the test point is prevented from being added to the node.
In U.S. Pat. No. 6,038,691, xe2x80x9cMethod Of Analyzing Logic Circuit Test Points, Apparatus for Analyzing Logic Circuit Test Points and Semiconductor Integrated Circuit with Test Points,xe2x80x9d to Nakao et al., several refinements to the test point insertion process are described. A cell replacement approach reduces the signal delay and area overhead involved when inserting control test points. A control-1 test point is naturally described as a two-input OR gate inserted into a signal, wherein the other input is fed by a scannable latch or primary input. A control-0 test point is naturally described as a two-input AND gate inserted into a signal, wherein the other input is fed by a scannable latch or primary input. Rather than inserting additional gates into a logic circuit, Nakao et al., define a table of acceptable cell replacements such that the insertion of a control-0 or control-1 test point is achieved by replacing a library cell with a given number of inputs (and type) with another cell having a different number of inputs (and type). For example, if a control-1 test point is added to a signal feeding an inverter, the inverter can be replaced with a two input NOR gate. This process reduces both the area and the signal delay imposed by insertion of test points.
An unacceptable signal delay is further reduced by the use of a table that describes paths and/or nodes or hierarchical entities in the circuit where insertion of test points is not allowed because there is insufficient slack in the path to allow additional logic gates to be inserted. Nodes in the circuit are not considered test point candidates if they appear in the table as separate nodes, or nodes along a specified path, or nodes within the specified hierarchical entity.
A further refinement to the test point insertion process taught by Nakao et al. is a method where test points may be inserted if they are not strongly correlated. Nakao et al. define the concept of strong and weak correlation between test points. Two observable points are said to be strongly correlated if their backward cones overlap. Two control points are said to be strongly correlated if their forward cones overlap. Two control points are said to be weakly correlated if they share common nodes whose observability is affected by both control points. Using this definition of correlation, the test point insertion process described is similar to the single test point insertion process pioneered by Seiss et al., except that instead of inserting the single test point providing the largest actual improvement in random pattern testability, the test points are ranked in descending order of actual improvement. The test point with the largest improvement is first inserted and its region of influence is recognized. Then, subsequent test points are inserted (in descending order of actual improvement) and their regions of influence is recognized as long as they are not strongly correlated with any of the previously chosen test points. This process continues until some maximum number of simultaneous test points is reached, or until the algorithm is terminated because of some other limit (such as maximum number of test points, desired random testability, etc.). Finally, the correlation information is also used by Nakao et al, to allow test points to share common scannable latches. Test points which are not correlated are allowed to share a common scannable latch. This reduces the number of scannable latches required.
The method taught by Seiss et al. has been demonstrated to be an effective tool for inserting test points on small circuits. However, given the large number of gates existing in today""s chip designs, the method of inserting one single test point at a time has proven to be impractical. Insertion of a single test point requires the evaluation of several candidate test points. The number of candidate test points assessed typically grows linearly with the size of the circuit. Furthermore, the evaluation of a single test point requires updates to the controllability and observability values for a subset of nodes forming the circuit. This process is also a linear function of the number of nodes. Therefore, the insertion of a single test point is a function of the square of the number of gates forming the circuit, expressed as O(g2), where g represents the number of gates. Assuming that 1 test point for every 1000 gates is to be inserted, its number is a linear function of the number of gates. This makes the entire test point insertion algorithm a cubic function of the number of gates (i.e., O(g3)). This approach runs into performance problems for circuits having several million gates. The work done by Lin and Cheng, while useful to the process of determining accurate test points, does not address the performance aspects of the algorithm. Tamarapalli et al. work is, likewise, also based on the single test point insertion strategy developed by Seiss et al., and displays the same performance problem.
Other related art includes an article by Jain, S. and V. Agrawal, xe2x80x9cStatistical Fault Analysis,xe2x80x9d IEEE Design Test Comput., Vol. 2, pp. 38-44, 1985; and an article by M. Srinivas and L. M. Patnaik, xe2x80x9cOn Generating Optimal Signal Probabilities for Random Tests: A Genetic Approach,xe2x80x9d VLSI Design, Vol. 4, No. 3, pp. 207-215, 1996.
The present invention is based on the use of a Genetic Algorithm. Basically, the genetic algorithm involves randomly generating several solutions to a problem. These solutions are referred to as individuals in the population. Each individual is evaluated for its fitness. Fit individuals (i.e., good solutions) are combined to form new individuals (hopefully, better solutions) which are added to the population. Weak individuals (i.e., poor solutions), are removed from the population. This series of steps is referred to as a generation and is repeated a number of times or until some xe2x80x9cbestxe2x80x9d solution is achieved. P. Mazumder and E. M. Rudnick in their textbook xe2x80x9cGenetic Algorithms for VLSI Design, Layout and Test Automationxe2x80x9d, published by Prentice Hall PTR, Upper Saddle River, N.J., 1999 provides a good summary on the use of genetic algorithms in other engineering applications.
It is an object of the invention to improve the testability of an IC by automatically inserting multiple additional test points at critical locations of the IC in order to gain supplemental controlability and/or observability.
It is another object to improve the testability of the IC by finding an optimal set of the test points concurrently rather that individually.
It is a further object to identify a set of test points efficiently and effectively for VLSI chips, modules, and the like, in parallel, using multiple processors.
It is still another object to identify a reduced set of potential candidate test points according to a variety of criteria such as cluster roots (i.e., nodes in the logic having poor controlability at the outputs, but good controlability at the inputs) by considering the inputs to the cluster roots as good test point candidates.
It is still a further object to take a large set of candidate points, divide them into subsets, evaluate various alternatives and solutions of the subsets, compare, combine and produce a new set of solutions, leading to a final set of optimum test points to be ultimately inserted into the circuit under test.
In a first aspect of the present invention, the controllability and observability of the nodes in the circuit is determined. The invention performs fault simulation of random patterns on the circuit to derive the initial controllability/observability information, and to determine which faults are easily tested by random patterns. Next, each node in the circuit is evaluated to measure the testability improvement if a test point were to be inserted at that node. Then, a measure of the circuit overall starting random pattern testability is derived from the controllability and observability information and from the list of faults that were not tested by random pattern simulation.
The actual test point identification process starts by identifying a set of candidate test points. The candidate test points are grouped into subsets (i.e., partial solutions) with each solution consisting of several candidate test points, evenly balanced as to the number of test points per solution. The number of test point candidates per solution and the number of partial solutions are functions of the number of gates in the circuit and the number of test points inserted. Based on their subsequent behavior, it is found that some will improve, some will deteriorate, leading to a final set of optimum test points to be ultimately inserted into the circuit under test. Each partial solution is evaluated to see what improvement it provides to the random pattern testability of the circuit. Once all the solutions have been evaluated, they are ranked according to the improvement they provide. Good solutions are then chosen to be recombined with other solutions to be added to the solution set, while poor solutions are eventually removed. This process is repeated until all of the desired test points have been inserted into the circuit
New solutions that are added to the solution set share some common test points with the solutions they were derived from. As solutions are recombined, more and more common test points propagate among the solutions. Over time, the test point solutions converge toward a single, common solution set. The process of recombining and evaluating solutions continues for a number of iterations or until the set of solutions stabilizes according to some measurement. One such example measurement is the percentage of solutions that are identical to the best solution (i.e., the one with the best testability improvement measurement).
Once the solution set converges, all of the test points in the best solution are inserted into the logic circuit by updating the controllability and observability of the nodes where test points are located, and by propagating the new controllability and observability information throughout the circuit. Then the testability measurement of the circuit is recomputed.
Since previous process derives only a subset of the desired test points, new candidate test points are derived and the process is repeated until all of the desired test points are inserted into the circuit.
In a second aspect of the invention, there is provided a method for analyzing an integrated circuit (IC) under test and for identifying and inserting test points in order to improve the testability of the IC, the method including the steps of: a) determining a measure of testability for the IC; b) selecting test point candidates to be evaluated for insertion in the IC and arranging the test point candidates into a first plurality of pairs of sets; c) evaluating the first plurality of pairs of sets and forming a second plurality of pairs of sets from the first plurality of pairs of sets, the evaluation being based on the respective testability improvement achieved by each plurality of the pairs of sets, and recombining the first and second plurality of pairs of sets based on results from the evaluation; and d) repeating step c) until the first and second pairs of sets converge to form the best set, i.e., the set providing the test points to be inserted into the IC.
In a third aspect of the invention, there is provided a method for analyzing an integrated circuit (IC) under test and for identifying and inserting potential test points in order to improve the testability of the IC, the method including the steps of: a) determining a measure of testability for the IC; b) forming a plurality of first sets of test points and determining the size and the number of the plurality of first sets; c) evaluating the improvement in the testability of the IC in the presence of the plurality of first sets of test points; d) performing an inversion and a mutation of the plurality of first sets of test point; e) intermingling pairs of the first plurality of sets to form a second plurality of pairs of sets with the intermingled pairs of the first plurality of sets; f) evaluating the second plurality of pairs of sets to select which first and second pairs of sets should be kept, the selected pairs of sets of the first and second plurality replacing the original first plurality of pairs of sets; and g) comparing the measure of testability for the IC to determine whether the selected plurality of first and second pairs of sets converges towards an optimal set of test points to be inserted in the IC.